package com.offer;

/**
 * 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，
 * 并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 * 示例 1:
 * <p>
 * 输入:
 * [
 *   [1,3,1],
 *   [1,5,1],
 *   [4,2,1]
 * ]
 * 输出: 12
 * 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
 */
public class offer47 {
    //方法一
    /* public int maxValue(int[][] grid) {
         int maxValue = 0;
         for (int i = 0; i < grid.length; i++) {
             for (int j = 0; j < grid[0].length; j++) {
                 if (i == 0 && j == 0) {
                     continue;
                 } else if (i == 0) {
                     grid[i][j] = grid[i][j] + grid[i][j - 1];
                 } else if (j == 0) {
                     grid[i][j] = grid[i][j] + grid[i - 1][j];
                 }else{
                     grid[i][j]=grid[i][j]+Math.max(grid[i-1][j],grid[i][j-1]);
                 }
             }
         }
         return grid[grid.length-1][grid[0].length-1];
     }*/
    //方法二
   /*public int maxValue(int[][] grid) {
       int row = grid.length;
       int column = grid[0].length;
       //dp[i][j]表示从grid[0][0]到grid[i - 1][j - 1]时的最大价值
       int[][] dp = new int[row + 1][column + 1];
       for (int i = 1; i <= row; i++) {
           for (int j = 1; j <= column; j++) {
               dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
           }
       }
       return dp[row][column];
   }*/
    //对方法一的优化，当矩阵大时，每次循环都会有一次判断，所以可以先对第一行和第一列进行初始化
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int j = 1; j < n; j++) { // 初始化第一行
            grid[0][j] += grid[0][j - 1];
        }
        for (int i = 1; i < m; i++) { // 初始化第一列
            grid[i][0] += grid[i - 1][0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
            }
        }
        return grid[m - 1][n - 1];
    }
}
